<?php
/*$m = 100;
$k = 100;
$fileName = '1000.txt';
$bloom = new Bloom($m, $k);
$file = fopen($fileName, 'r');
while (!feof($file)) {
	$key = fgets($file);
	$bloom->addKey($key);
}
fclose($file);*/

class Bloom {
	private $p;
	private $m;
	private $constants;
	private $levels;
	
	public function __construct($m, $k) {
		$this->m = $m;
		$this->k = $k;
		$this->p = $this->getNextPrime($this->m);
		$this->constants = array();
		$this->generateNumberOfConstants($this->k);
		$this->generateNumberOfLevels($this->k);
	}
	
	private function generateHash($x, $a, $b) {
		
		return fmod(fmod($a * $x + $b, $this->p), $this->m); 
	}
	
	public function addKey($x) {
		for ($i = 0; $i < $this->k; $i++) {
			list($a, $b) = $this->constants[$i];
			$position = $this->generateHash($x, $a, $b);
			$this->levels[$i][$position] = 1;
		}
	}
	
	public function query($x) {
		$exists = 0;
		for ($i = 0; $i < $this->k; $i++) {
			list($a, $b) = $this->constants[$i];
			$position = $this->generateHash($x, $a, $b);
			echo $position . '<br>';
			var_dump($this->levels[$i][$position]);
			$exists |= $this->levels[$i][$position];
		}

		return (bool)$exists;
	}
	
	private function getNextPrime($value) {
		$isPrime = false;
		$prime = $this->p;
		for ($i = $value + 1; $i < 2 * $value; $i++) {
			if ($this->isPrime($i)) {
				$prime = $i;
				break;
			}
		}
		
		return $prime;
	}
	
	private function isPrime($value) {
		for ($i = 2; $i < $value; $i++) {
			if ($value % $i == 0) {
				return false;
			}
		}
		
		return true;
	}
	
	// Needs to be unique
	private function generateNumberOfConstants($n = 10) {
		while ($n > 0) {
			list($a, $b) = $this->generateConstants();
			$alreadyExist = false;
			foreach ($this->constants as $constants) {
				if (
					$constants[0] == $a && $constants[1] == $b ||
					$constants[0] == $b && $constants[1] == $a
				) {
					$alreadyExist = true;
					break;
				}
			}
			
			if (!$alreadyExist) {
				$this->constants[] = array ($a, $b);
				$n--;
			}
		}
	}
	
	private function generateConstants() {
		
		return array(mt_rand(1, $this->p - 1), mt_rand(0, $this->p - 1));
	}
	
	private function generateNumberOfLevels($n = 10) {
		for ($i = 0; $i < $n; $i++) {
			$this->levels[$i] = array();
			for ($j = 0; $j < $this->m; $j++) {
				$this->levels[$i][$j] = 0; 
			}
		}
	}
	
	public function getLevels() {
		
		return $this->levels;
	}
}